/*
 * @lc app=leetcode.cn id=141 lang=golang
 *
 * [141] 环形链表
 */

// 3. 哈希
// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
	m := map[*ListNode]int{}
	for head != nil {
		if _, ok := m[head]; ok {
			return true
		}
		m[head] = 1
		head = head.Next
	}
	return false
}

// @lc code=end

// 2-2. 每次都指向自己（递归），一旦（head == head.Next）就有环
// 不过会改变链表的结构
// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return false
	}
	if head == head.Next {
		return true
	}
	next := head.Next
	head.Next = head
	return hasCycle(next)
}

// @lc code=end

// 2-1. 每次都指向自己（迭代），一旦（head == head.Next）就有环
// 不过会改变链表的结构
// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
	for head != nil {
		if head == head.Next {
			return true
		}
		next := head.Next
		head.Next = head
		head = next
	}

	return false
}

// @lc code=end

// 1. 快慢指针
// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next

		if slow == fast {
			return true
		}
	}
	return false
}

// @lc code=end

